// poj 2907
// complexisity: n^2*2^n

#include <iostream>
#include <limits>
#include <algorithm>
using namespace std;


const int N = 11;
int n;
int x[N], y[N];
#define MDIST(i, j) (abs(x[i] - x[j]) + abs(y[i] - y[j]))

// dp[S][k], have visited all cities in set S, the last city visited is k
// use bit to identify whether a city is in set S.
int dp[1 << N][N];

// the city before the last.
int trace[1 << N][N];

int solve(int s, int k)
{
	if (dp[s][k] == -1)
	{
		int ss = s & ~(1 << k);
		if (ss == 0)
			dp[s][k] = 0;
		else
		{
			int min_dist = numeric_limits<int>::max();
			int p;
			for (int i = 0; i < n; ++i)
			{
				int mask = (1 << i);
				if (ss & mask)
				{
					int dist = solve(ss, i) + MDIST(i, k);
					if (dist < min_dist)
					{
						p = i;
						min_dist = dist;
					}
				}
			}
			dp[s][k] = min_dist;
			trace[s][k] = p;
		}
	}
	return dp[s][k];
}

int main()
{
	int cn;
	scanf("%d", &cn);
	while (cn--)
	{
		int sx, sy;
		scanf("%d%d", &sx, &sy);
		scanf("%d%d", &sx, &sy);
		scanf("%d", &n);
		for (int i = 0; i < n; ++i)
			scanf("%d%d", x + i, y + i);
		x[n] = sx, y[n] = sy;
		++n;
		memset(dp, 0xFF, sizeof(dp));
		memset(trace, 0xFF, sizeof(trace));

		int ans = numeric_limits<int>::max();
		for (int i = 0; i < n; ++i)
		{
			solve((1 << n) - 1, i);
			// find the starting point
			int first = i;
			int s = (1 << n) - 1;
			while (trace[s][first] != -1)
			{
				int prev = trace[s][first];
				s &= ~(1 << first);
				first = prev;
			}
			int dist = solve((1 << n) - 1, i) + MDIST(first, i);
			ans = min(ans, dist);
		}
		printf("The shortest path has length %d\n", ans);
	}
	system("pause");
	return 0;
}